package sorter;

/**
 * 适用于：非负整数。
 * 基数排序：首先计算出数组中最大值的位数 digits，对数组进行 digits 轮排序，即先按个位排序、再按十位排序...，直到按最大位排序。
 * 时间复杂度：对每一轮排序，都需要先收集后释放所有元素，因此时间复杂度O(k*n)。k 为最大元素的位数。
 * 稳定性：稳定。
 * @author Zhang Ziyi
 */
public class RadixSorter implements Sorter{
    @Override
    public void sort(int[] arr) {
        // 计算数组最大值的位数
        int digits = countDigit(arr);
        // 基数桶，横坐标：0~9表示位值，每行都存储了一些元素
        int[][] buckets = new int[10][arr.length];
        // 标记每个基数桶中存储了多少个元素
        int[] bucketCount = new int[10];
        // 对数组进行 digits 轮排序
        for (int i = 0, n = 1; i < digits; i++, n *= 10) {
            // 收集
            for (int num : arr) {
                int bucketIndex = (num / n) % 10;
                buckets[bucketIndex][bucketCount[bucketIndex]++] = num;
            }
            // 释放
            int index = 0;
            for (int j = 0; j < buckets.length; j++) {
                for (int k = 0; k < bucketCount[j]; k++) {
                    arr[index++] = buckets[j][k];
                }
            }
            // 清空 bucketCount
            clearBucket(bucketCount);
        }
    }

    private void clearBucket(int[] bucketCount) {
        for (int i = 0; i < bucketCount.length; i++) {
            bucketCount[i] = 0;
        }
    }

    /**
     * 计算数组中最大值的位数
     * @param arr
     * @return
     */
    private int countDigit(int[] arr) {
        // 找到最大值
        int max = findMax(arr);
        // 获取位数
        return getDigits(max);
    }

    /**
     * 获取 num 的位数
     */
    private int getDigits(int num) {
        int digits = 1;
        while (num > 10) {
            num /= 10;
            digits++;
        }
        return digits;
    }

    /**
     * 找到数组中的最大值
     */
    private int findMax(int[] arr) {
        int max = arr[0];
        for (int num : arr) {
            max = num > max ? num : max;
        }
        return max;
    }

}
